1. Field of the Invention
The present invention generally relates to an entropy decoder, and more particularly, to an adaptive canonical Huffman decoder and a method thereof, and a video decoder using the adaptive canonical Huffman decoder and the method thereof.
2. Description of Related Art
Huffman coding is an entropy coding usually applied to image or video compression, and which is a long-standing lossless compression technique. However, if Huffman coding is adopted, a decoder has to know the structure of a Huffman coding tree, and accordingly the encoder has to transmit a Huffman coding tree to the decoder in a bit stream, or the decoder has to use a Huffman coding tree pre-established between the decoder and an encoder.
However, the quantity of data to be compressed has been increasing along with the development of information technology. Thus, the data compression rate will be drastically reduced if a Huffman coding tree is transmitted in a bit stream. Even though this problem can be resolved by storing the Huffman coding tree in the decoder in advance, too much hardware resource of the decoder will be taken up by the large Huffman coding tree.
In order to resolve foregoing problem, a canonical Huffman coding concept is brought forward by Schwartz (1964). Same as Huffman coding, the canonical Huffman coding also belongs to the optimal prefix coding and the variable length coding. The canonical Huffman coding is a subset of the Huffman coding, and the major feature thereof is that some compulsory assumptions are added into the Huffman coding such that a decoder can re-construct an entire Huffman coding tree with very little information.
The most important assumption of canonical Huffman coding is the assumption of a numerical sequence property. This assumption specifies that all the codewords having the same length are continuous binary digits. For example, if a first code having a codeword length of 4 is 0010, the other codewords having a codeword length of 4 must be 0011, 0100, 0101, etc. Besides this assumption of numerical sequence property, other assumptions are also specified in the canonical Huffman coding. Canonical Huffman coding is divided into a first type of canonical Huffman coding and a second type of canonical Huffman coding according to these assumptions.
The conventional canonical Huffman coding usually adopts a software decoding method. However, the codeword lengths are determined sequentially in the software decoding method. As a result, when the codeword lengths are large, the software decoding method may not be efficient enough to be applied to some systems (for example, real-time systems) with higher speed requirement.
In the U.S. Pat. No. 5,173,695, a hardware decoder is provided by Ming-Ting Sun for decoding a variable length code. Since canonical Huffman coding is also a variable length coding, the hardware decoder may also be applied to the decoding of canonical Huffman codes. FIG. 1A is a schematic block diagram of a canonical Huffman decoder 10 implemented according to the U.S. Pat. No. 5,173,695. Referring to FIG. 1A, the conventional decoder 10 includes registers 101 and 102, a barrel register 103, an adder 104, and a lookup table 11. The lookup table 11 includes a codeword table 110, a decoded symbol table 111, and a codeword length table 112. The coupling relationship between foregoing components of the canonical Huffman decoder 10 is as shown in FIG. 1A and therefore will not be described herein.
The conventional decoder 10 compares an input bit stream with the codeword table 110 in parallel and outputs the obtained codeword lengths and decoded symbols. The codeword table 110, the codeword length table 112, and the decoded symbol table 111 are all stored in a programmable logic array. Thus, the decoding speed of the conventional decoder 10 is very fast. The conventional decoder 10 can decode one symbol during each clock cycle (1 symbol/cycle) and accordingly can meet the requirement of many real-time systems.
However, along with the advancement of encoding algorithm, a content adaptive concept is brought forward. According to the content adaptive concept, the probability distributions of different symbols are different in different encoding environments. Thus, an encoder uses different encoding tables for encoding a code in different environments. As a result, the decoder has to use the corresponding encoding table for decoding the code. For example, in the VC-1 specification, there are totally 8 alternating current (AC) encoding tables, and which AC encoding table is used for encoding a code is determined according to a quantization parameter (QP), an inter-frame difference, or an intra-frame difference.
Many recent video encoding standards (for example, H.264 and VC-1) adopt this content adaptive concept. If a content adaptive decoder is to be implemented according to the concept provided by the U.S. Pat. No. 5,173,695, an encoding table selection signal and two multiplexers have to be added to select a correct decoded symbol.
FIG. 1B is a schematic block diagram of a content adaptive decoder 20 implemented according to the U.S. Pat. No. 5,173,695. Referring to FIG. 1B, the decoder 20 includes registers 201 and 202, a barrel register 203, an adder 204, a first lookup table 21, a second lookup table 22, a third lookup table 23, a fourth lookup table 24, and multiplexers 205 and 206. The first through the fourth lookup tables 21˜24 store the contents of corresponding encoding tables. For example, the first lookup table 21 stores the codeword table, decoded symbol table and codeword length table in the corresponding encoding table. The coupling relationship between foregoing components of the decoder 20 is as shown in FIG. 1B and therefore will not be described herein.
The decoder 20 compares an input bit stream with a programmable logic array in parallel. Each of the lookup tables 21˜24 outputs a decoded symbol and a codeword length, and an encoding table selection signal Table_sel is used for controlling the multiplexers 205 and 206 to select a correct decoded symbol and codeword length. However, the hardware cost of this implementation increases in proportion along with the increase of encoding tables. Even though this implementation can be applied to all variable length decoding and is easy to realize, the hardware cost thereof when applied to content adaptive coding is drastically increased.
Even though the decoder provided by U.S. Pat. No. 5,173,695 offers a high decoding speed and is easy to implement, and which may even be implemented as any variable length decoder, because the implementation of a canonical Huffman decoder does not benefit from the feature of canonical Huffman coding that it is not necessary to store an entire Huffman coding tree, the hardware cost will be much high to implement a canonical Huffman decoder according to the U.S. Pat. No. 5,173,695.
Accordingly, a canonical Huffman decoder is provided in U.S. Pat. No. 6,657,569 by Mark L. Barnett, wherein which the decoding speed is increased by using the hardware acceleration manner. FIG. 2 is a schematic block diagram of a canonical Huffman decoder 30 according to the U.S. Pat. No. 6,657,569. Referring to FIG. 2, the canonical Huffman decoder 30 includes a first code register 301, a symbol pointer register 302, comparators 330˜33N, subtractors 350˜35N, adders 340˜34N, and a multiplexer 312. The coupling relationship between foregoing components of the canonical Huffman decoder 30 is as shown in FIG. 2 and therefore will not be described herein.
An external memory records a plurality of different encoding tables, and each of the encoding tables has a corresponding first code table, symbol pointer table, and symbol table. The first code register 301 selects a first code table corresponding to the current encoding table from a plurality of first code tables stored in the external memory, wherein the selected first code table records first codes FIRSTCODE[0]˜FIRSTCODE[N] having their codeword lengths from 1 to N+1. The symbol pointer register 302 selects a symbol pointer table corresponding to the current encoding table from a plurality of symbol pointer tables stored in the external memory. The symbol pointer register 302 only stores the symbol pointers SYM_PTR[0]˜SYM_PTR[N] of a plurality of first codes corresponding to the first code register 301, wherein SYM_PTR[i] represents the symbol pointer of a first code having a codeword length of i+1, wherein i is an integer between 0 and N.
The canonical Huffman decoder 30 compares all the first codes with an input bit stream according to the feature of canonical Huffman coding and then selects a correct codeword length and address signal by using the multiplexer 312. Finally, the canonical Huffman decoder 30 obtains a correct decoded symbol from the external memory according to the address signal.
Because both the input and output of the canonical Huffman decoder 30 need to access the external memory, in a system using the canonical Huffman decoder 30, the rights of all memory accesses is determined through the arbitration of an arbiter. As a result, the canonical Huffman decoder 30 has a low decoding speed. Thus, the canonical Huffman decoder 30 may not be able to meet the speed requirement of some real-time systems. In addition, the canonical Huffman decoder 30 can only decode second type of canonical Huffman codes, and when the canonical Huffman decoder 30 is applied to a video decoder, the decoding information of a corresponding encoding table is always updated after a frame is decoded in consideration of the decoding speed. Thereby, the canonical Huffman decoder 30 is not very adaptable in its application.